package 动态规划;

import java.util.List;
/*
    题目描述
    给定一个字符串s和一个词典wordDict，确定s是否可以根据词典中的词分成一个或多个单词。
    比如，
    给定 s = "leetcode"
    wordDict = ["leet", "code"]
    返回true，因为"leetcode"可以被分成"leet code"
*/

public class LeetCode139_单词拆分 {
    /*
    状态：
        子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
        F(i): 前i个字符能否根据词典中的词被成功分词
    状态递推：
        F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
        在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，
        则F(i)为true
    初始值：
        对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
        空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
        的例子进行验证
        F(0) = true
    返回结果：F(n)
    */

    //注意边界值问题，因为在字符串中存储是从0下标开始，而在数组中实际是从1开始、arr[0]为辅助--用来判断
    public boolean wordBreak(String s, List<String> dict) {
        boolean[] canBreak = new boolean[s.length() + 1];
        // 初始化F(0)=true
        canBreak[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            // true{j < i && F(j) && substr[j+1,i]能在词典中找到}
            for (int j = 0; j < i; j++) {
                // F(j): 之前的字符串已经确定了可以有从集合中找到分割串的结果为true
                // 如果从[j+1, i]这个子串也在集合中，那么相对的 F(i) 就找到了结果，为true
                if (canBreak[j] && dict.contains(s.substring(j, i))) { //substring左闭右开且字符向前挪一个
                    // 通过前面已知的 F(j) 从小到大来求 F(i)
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }

}
